package DynamicProgramming;
/*
 * 不同的子序列
 */
public class lc115 {

        public int numDistinct(String s, String t) {
            char[] S = s.toCharArray();
            char[] T = t.toCharArray();
            int lens = S.length;
            int lent = T.length;
            int[][] dp = new int[lens + 1][lent + 1];
            for (int i = 0; i <= lens; i++) {
                dp[i][0] = 1;
            }
            for (int i =1; i <= lens; i++) {
                for (int j = 1; j <= lent; j++) {
                    if (S[i - 1] == T[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            return dp[lens][lent];
        }
    
}
